package oj.oj_155;

import java.util.*;

public class MinStack正确3 {
    static class Element {
        int e;
        int count;

        Element(int e) {
            this.e = e;
            this.count = 1;
        }

        public void increment() {
            this.count++;
        }

        public boolean decrement() {
            this.count--;
            return this.count == 0;
        }

        @Override
        public String toString() {
            return String.format("{ e: %d, count: %d }", e, count);
        }
    }

    private final Deque<Integer> normalStack = new LinkedList<>();
    private final Deque<Element> minStack = new LinkedList<>();

    public void push(int val) {
        normalStack.push(val);

        if (minStack.isEmpty()) {
            minStack.push(new Element(val));
        } else if (val < minStack.peek().e) {
            minStack.push(new Element(val));
        } else if (val == minStack.peek().e) {
            minStack.peek().increment();
        }
    }

    public void pop() {
        if (normalStack.isEmpty()) {
            return;
        }

        int val = normalStack.peek();
        if (val == minStack.peek().e) {
            if (minStack.peek().decrement()) {
                minStack.pop();
            }
        }

        normalStack.pop();
    }

    public static void main(String[] args) {
        MinStack正确3 stack = new MinStack正确3();

        stack.push(5);
        stack.push(3);
        stack.push(7);
        stack.push(1);
        stack.push(1);
        stack.push(0);

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
    }
}
